Due to the nature of flash memory in solid state drives (SSDs), data is typically programmed by pages and erased by blocks. A page in an SSD is typically 8-16 kilobytes (KB) in size and a block consists of a large number of pages (e.g., 256 or 512). Thus, a particular physical location in an SSD (e.g., a page) cannot be directly overwritten without overwriting data in pages within the same block, as is possible in a magnetic hard disk drive. As such, address indirection is needed. Conventional data storage device controllers, which manage the flash memory on data storage devices such as SSDs and interface with the host system, use a Logical to Physical (L2P) mapping system known as Logical Block Addressing (LBA) that is part of the flash translation layer (FTL). When new data comes in replacing older data already written, the data storage device controller causes the new data to be written in a new location and update the logical mapping to point to the new physical location. Since the old physical location no longer holds valid data, it will eventually need to be erased before it can be written again.
Conventionally, a large L2P map table maps logical entries to physical address locations on an SSD. This large L2P map table, which may reside in a volatile memory such as dynamic random access memory (DRAM), is usually updated as writes come in, and saved to non-volatile memory in small sections. For example, if random writing occurs, although the system may have to update only one entry, it may nonetheless have to save to the non-volatile memory the entire table or a portion thereof, including entries that have not been updated, which is inherently inefficient.
FIG. 1 shows aspects of a conventional Logical Block Addressing (LBA) scheme for an SSD. As shown therein, a map table 104 contains one entry for every logical block 102 defined for the data storage device's flash memory 106. For example, a 64 GB SSD that supports 512 byte logical blocks may present itself to the host as having 125,000,000 logical blocks. One entry in the map table 104 contains the current location of each of the 125,000,000 logical blocks in the flash memory 106. In a conventional SSD, a flash page holds an integer number of logical blocks (i.e., a logical block does not span across flash pages). In this conventional example, an 8 KB flash page would hold 16 logical blocks (of size 512 bytes). Therefore, each entry in the logical-to-physical map table 104 contains a field 108 identifying the flash die on which the logical block is stored, a field 110 identifying the flash block on which the logical block is stored, another field 112 identifying the flash page within the flash block and a field 114 identifying the offset within the flash page that identifies where the logical block data begins in the identified flash page. For example, a conventional 8 KB flash page 119 may hold 16 logical blocks of a constant predetermined size of, for example, 512 bytes. Therefore, each entry in the logical-to-physical map table 104 contains a Page Offset field that identifies the 512 byte “bucket” where a logical block's data begins in the flash page (e.g., at byte 512*Page Offset). For example, the data for logical block 4 begins within the current flash page at byte 512*4. Similarly, the data for logical block 11 begins within the current flash page at byte 512*11. Therefore, each conventional flash page 105 is configured to hold the data for a predetermined and invariant integer number of logical blocks. The size of each logical block is, therefore, fixed. Moreover, the data for each logical block is aligned with a 512 byte boundary. That is, the data for any given logical block conventionally must be aligned with the sector size boundaries (such as the 512 byte boundaries) within a flash page. Therefore, the data for a given logical block may not start or end at other than an integer multiple of the sector size, as illustrated at 116. This also implies that conventionally, the data for a logical block may not cross flash page boundaries 117, as shown at 118.